algo - spiral traversal.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Traversing through a square matrix\n",
    "\n",
    "Author: katychuang\n",
    "\n",
    "Practicing an algo problem with python. Starting at (0,0), the sequence is:\n",
    "\n",
    "* 1 step up, 1 step right\n",
    "* 2 steps down, 2 steps left\n",
    "* 3 steps up, 3 steps right\n",
    "\n",
    "..and so on\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# takes a step and moves on\n",
    "def move((x, y), direction):\n",
    "    if direction == \"up\":\n",
    "        y += 1\n",
    "    if direction == \"down\":\n",
    "        y -= 1\n",
    "    if direction == \"right\":\n",
    "        x += 1\n",
    "    if direction == \"left\":\n",
    "        x -= 1\n",
    "    return (x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# decides on direction\n",
    "def change(index):\n",
    "    if index > 2:\n",
    "        return 0\n",
    "    else: \n",
    "        return index+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# input n number of steps and output coordinates\n",
    "def spiral(n, directions=[\"up\", \"right\", \"down\", \"left\"]):\n",
    "    ind = 0\n",
    "    s = steps_taken = 0\n",
    "    step_level = 1\n",
    "    x = y = 0\n",
    "\n",
    "    if n == 0:\n",
    "        return ()\n",
    "    elif n == 1:\n",
    "        return (0, 0)\n",
    "    elif n == 2:\n",
    "        return (0, 1)\n",
    "    else:\n",
    "        # print \"{}\".format(n)\n",
    "        while steps_taken < n:\n",
    "            \n",
    "            # keep moving in direction until step level reached\n",
    "            while s < step_level:\n",
    "                (x, y) = move((x, y), directions[ind])\n",
    "                steps_taken += 1\n",
    "                s += 1\n",
    "                \n",
    "                # print \"{}: {} \\t [{} steps of {} {}]\".format(steps_taken, (x, y), s, step_level, directions[ind])\n",
    "\n",
    "                if steps_taken == n:\n",
    "                    return (x, y)\n",
    "\n",
    "            # reset step counter, if right/left add incr step level\n",
    "            s = 0\n",
    "            if ((ind == 1) or (ind == 3)): step_level += 1\n",
    "\n",
    "            # reaching step level means changing direction\n",
    "            ind = change(ind)\n",
    "\n",
    "    return (x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#test the output for a few use cases"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 steps: (1, 0)\n",
      "4 steps: (1, -1)\n",
      "5 steps: (0, -1)\n",
      "6 steps: (-1, -1)\n"
     ]
    }
   ],
   "source": [
    "for x in range(3, 7):\n",
    "    print \"{} steps: {}\".format(x, spiral(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}